#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    int smallestNumber(int n, int t){
        auto check=[&](int x){
            int prod=1;
            for(;x;x/=10) prod*=x%10;
            return prod%t==0;
        };
        for(int i=n;;i++)if(check(i))return i;
    }
};

class Solution2{
public:
    int maxFrequency(vector<int> nums, int k,int numOperations){
        unordered_set<int> st; unordered_map<int,int>mp;
        for(int x:nums){
            st.insert(x); st.insert(x-k); st.insert(x+k);
            mp[x]++;
        }
        sort(nums.begin(),nums.end());
        int ans=0;
        for(int x:st){
            int tmp=0;
            tmp+= upper_bound(nums.begin(),nums.end(),x+k)- upper_bound(nums.begin(),nums.end(),x);
            tmp+= lower_bound(nums.begin(),nums.end(),x)- lower_bound(nums.begin(),nums.end(),x-k);
            tmp=min(tmp,numOperations);
            ans=max(ans, mp[x]+tmp);
        }
        return ans;
    }
};

class Solution3{
public:
    int maxFrequency(vector<int>& nums, int k, int numOperation){
        unordered_map<int, int> cnt;
        map<int,int> diff;
        for(int x: nums){
            cnt[x]++;
            diff[x];
            diff[x-k]++;
            diff[x+k+1]--;
        }
        int ans=0, sum_d=0;
        for(auto& [x,d]:diff){
            sum_d+=d;
            ans=max(ans, min(sum_d,cnt[x]+numOperation));
        } return ans;
    }
};

// 超时了，看下面的方法二吧
class Solution4 {
public:
    string smallestNumber(string s, long long t) {
        long long tmp = t;
        int cnt = 0;
        for (int p : {2, 3, 5, 7}) {
            while (tmp % p == 0) {
                tmp /= p;
                cnt++;
            }
        }
        if (tmp > 1) {
            return "-1";
        }
        cnt = max(cnt - (int) s.length() + 1, 1);
        s = string(cnt, '0') + s;

        int n = s.length();
        string ans(n, '0');
        vector<unordered_set<long long>> vis(n);
        auto dfs = [&](auto&& dfs, int i, long long t, bool is_limit) -> bool {
            if (i == n) {
                return t == 1;
            }
            if (!is_limit && !vis[i].insert(t).second) {
                return false;
            }

            if (is_limit && i < cnt && dfs(dfs, i + 1, t, true)) { // 填 0（跳过）
                return true;
            }

            int low = is_limit ? s[i] - '0' : 0;
            for (int d = max(low, 1); d <= 9; d++) {
                if (dfs(dfs, i + 1, t / gcd(t, d), is_limit && d == low)) {
                    ans[i] = '0' + d;
                    return true;
                }
            }
            return false;
        };
        dfs(dfs, 0, t, true);

//        auto it = ranges::find_if(ans, [](char c) { return c != '0'; });
//        int it;
//        for(auto a: ans) {
//            if(a!='0') {
//                it=a;
//                break;
//            }
//        }
//        return string(it, ans.end()); // 去掉前导零
    }
};


int main(){
    Solution s; cout<<s.smallestNumber(10,2)<<endl;

    vector<int> nums2={1,4,5};
    Solution2 s2; cout<<s2.maxFrequency(nums2, 1,2)<<endl;

    vector<int> nums3={1,4,5};
    Solution3 s3; cout<<s3.maxFrequency(nums3, 1,2)<<endl;




}